括号的匹配

题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
题意描述： 在算术表达式中，除了加、减、乘、除等运算外，往往还有括号。包括有大括号{}，中括号[]，小括号()，尖括号<>等。 对于每一对括号，必须先左边括号，然后右边括号；如果有多个括号，则每种类型的左括号和右括号的个数必须相等；对于多重括号的情形，按运算规则，从外到内的括号嵌套顺序为：大括号->中括号->小括号->尖括号。例如，{[()]}，{()},{{}}为一个合法的表达式，而([{}])，{([])},[{<>}]都是非法的。

输入描述:
文件的第一行为一个整数n（1≤n≤100），接下来有n行仅由上述四类括号组成的括号表达式。第i+1行表示第i个表达式。每个括号表达式的长度不超过255。
输出描述:
在输出文件中有N行，其中第I行对应第I个表达式的合法性，合法输出YES，非法输出NO。

输入样例#:
5
{[(<>)]}
[()]
<>()[]{}
[{}]
{()}

输出样例#:
YES
YES
YES
NO
YES

题目来源
中山大学2019年机试题


#include<bits/stdc++.h>
using namespace std;

int val[128];

int main(){
    val['<']=1,val['(']=2,val['[']=3,val['{']=4;//优先级
    int n;
    string str;
    scanf("%d",&n);
    while(n--){
        cin>>str;
        stack<char> a;
        int flag=0;
        for(int i=0;i<str.size();++i){
            if(!a.empty()){
                if((str[i]=='('||str[i]=='['||str[i]=='{'||str[i]=='<')
                    &&(val[a.top()]<val[str[i]])){//优先级出错
                    flag=1;
                }else if((a.top()=='('&&str[i]==')')||(a.top()=='['&&str[i]==']')||
                   (a.top()=='{'&&str[i]=='}')||(a.top()=='<'&&str[i]=='>')){//该次匹配成功
                    a.pop();
                }else{
                    a.push(str[i]);
                }
            }else{
                a.push(str[i]);
            }
        }
        if(flag==1){
            printf("NO\n");
        }else if(a.empty()){
            printf("YES\n");
        }else{
            printf("NO\n");
        }
    }
    return 0;
}
